Misi Anda 🎯
Sambungkan kembali $N$ planet, yang diberikan sebagai koordinat 2D, dengan jaringan "Hyper-lane" berbiaya terendah.
- Tujuan: Hubungkan semua $N$ planet (simpul) agar semuanya dapat diakses (secara langsung atau tidak langsung).
- Tujuan: Temukan desain jaringan yang meminimalkan **biaya total**.
Analisis 🛰️
Biaya sebuah jalur (sisi) adalah jarak Euclidean:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Jalur dapat dibangun antara setiap dua planet.
- Artinya kita memiliki graf lengkap (padat).
Solusinya ⚙️
Ini adalah masalah klasik Pohon Rentang Minimum (MST).
- Algoritma: Petunjuk menyarankan Algoritma Prim (versi $O(V^2)$), yang sangat cocok untuk graf padat).
- Titik Awal: Kita akan memulai algoritma dari Planet 0 untuk hasil yang konsisten.
Graf lengkap (kiri) memiliki semua sisi yang mungkin. MST (kanan) adalah himpunan sisi paling murah yang menghubungkan semua simpul.